package graph.day14;

public class Leetcode_234 {

    public boolean isPalindrome(ListNode head) {
        // 如果为空或者仅有一个节点，返回true
        if (head == null || head.next == null) return true;
        ListNode slow = head;
        ListNode fast = head;
        ListNode pre = head;
        while (fast != null && fast.next != null) {
            pre = slow;  // 记录slow的前一个结点
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;  // 分割两个链表

        // 前半部分
        ListNode cur1 = head;
        // 后半部分，这里使用了反转链表
        ListNode cur2 = reverseList(slow);

        while (cur1 != null) {
            if (cur1.val != cur2.val) return false;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return true;
    }

    ListNode reverseList(ListNode head) {
        ListNode tmp;
        ListNode pre = null;
        while (head != null) {
            tmp = head.next;
            head.next = pre;
            pre = head;
            head = tmp;
        }
        return pre;
    }
}
